package main

import "fmt"

func main() {
	data := []int{3, 2, 4, 5, 1, 1}
	//quickSort(data, 0, len(data)-1)
	//bubbleSort(data)
	//heapSort(data)
	fmt.Println(mergeSort(data))
	fmt.Println(data)
}

func bubbleSort(arr []int) {
	l := len(arr)
	for i := 1; i < l; i++ {
		doSwap := false
		for j := 0; j < l-i; j++ {
			if arr[j] < arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				doSwap = true
			}
		}
		if !doSwap {
			return
		}
	}
}

func heapSort(arr []int) {
	//建堆
	buildHeap(arr)
	//排序
	l := len(arr)
	for i := l - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, 0, i)
	}
}

func buildHeap(arr []int) {
	l := len(arr)
	for i := (l - 2) / 2; i >= 0; i-- {
		heapify(arr, i, l)
	}
}

func heapify(arr []int, i int, l int) {
	t := i
	left := 2*i + 1
	right := left + 1

	if left < l && arr[t] > arr[left] {
		t = left
	}
	if right < l && arr[t] > arr[right] {
		t = right
	}

	if t != i {
		arr[t], arr[i] = arr[i], arr[t]
		heapify(arr, t, l)
	}
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func quickSort(arr []int, lo int, hi int) {
	if lo >= hi {
		return
	}

	p := partition(arr, lo, hi)
	quickSort(arr, lo, p-1)
	quickSort(arr, p+1, hi)
}

func partition(arr []int, lo int, hi int) int {
	j := lo - 1
	for i := lo; i < hi; i++ {
		if arr[i] < arr[hi] {
			j++
			arr[j], arr[i] = arr[i], arr[j]
		}
	}

	arr[j+1], arr[hi] = arr[hi], arr[j+1]
	return j + 1
}

func mergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	m := len(arr) / 2
	left := mergeSort(arr[:m])
	right := mergeSort(arr[m:])
	return merge(left, right)
}

func merge(a, b []int) []int {
	tmp := []int{}
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] < b[j] {
			tmp = append(tmp, a[i])
			i++
		} else {
			tmp = append(tmp, b[j])
			j++
		}
	}

	if i < len(a) {
		tmp = append(tmp, a[i:]...)
	}

	if j < len(b) {
		tmp = append(tmp, b[j:]...)
	}

	return tmp
}
